package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
 *
 * @Author: haogege
 * @Date: 2021/8/28
 */
public class _121_买卖股票的最佳时机 {

    public static void main(String[] args) {
        _121_买卖股票的最佳时机 v = new _121_买卖股票的最佳时机();
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(v.maxProfit(prices));
    }

    // 使用动态规划解决问题，转换成最大连续子序列和
    public int maxProfit(int[] prices) {
        if (prices.length == 1) return 0;
        int len = prices.length;
        int[] result = new int[len - 1];
        for (int i = 1; i < len; i++) {
            result[i - 1] = prices[i] - prices[i - 1];
        }

        // 寻找到最大连续子序列和
        int subMax = result[0];
        int max = subMax;
        for (int i = 1; i < result.length; i++) {
            subMax = Math.max(subMax + result[i], result[i]);
            max = Math.max(max, subMax);
        }
        return Math.max(0, max);
    }

    public int maxProfit4(int[] prices) {
        int min = prices[0];
        int max = 0;
        int len = prices.length;
        for (int i = 1; i < len; i++) {
            if (prices[i] > min) {
                max = Math.max(prices[i] - min, max);
            } else {
                min = prices[i];
            }
        }
        return max;
    }

    // dp数组内存优化
    public int maxProfit3(int[] prices) {
        if (prices.length == 1) return 0;
        // 计算相邻两天的差值
        int[] nums = new int[prices.length - 1];
        for (int i = 1; i < prices.length; i++) {
            nums[i - 1] = prices[i] - prices[i - 1];
        }
        int dp = nums[0];
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            // 判断dp[i - 1]为大于0
            if (dp > 0) {
                dp = dp + nums[i];
            } else {
                dp = nums[i];
            }
            max = Math.max(max, dp);
        }
        return Math.max(max, 0);
    }

    // 动态规划
    public int maxProfit2(int[] prices) {
        if (prices.length == 1) return 0;
        // 计算相邻两天的差值
        int[] nums = new int[prices.length - 1];
        for (int i = 1; i < prices.length; i++) {
            nums[i - 1] = prices[i] - prices[i - 1];
        }
        // 装换成求数组的最大连续子序列和, dp[i]代表前i项的最大连续子序列和
        int[] dp = new int[nums.length + 1];
        // 设定初始值
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            // 判断dp[i - 1]为大于0
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return Math.max(max, 0);
    }

    // 元素迭代
    public int maxProfit1(int[] prices) {
        int min = prices[0];
        int profit = 0;
        for (int price : prices) {
            if (price > min) {
                // 计算利润
                profit = Math.max(price - min, profit);
            } else {
                // 设置最小值
                min = price;
            }
        }
        return profit;
    }
}
